package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {

    List<List<Integer>> lists = new ArrayList<>();

    public static void main(String[] args) {
        CombinationSum combinationSum = new CombinationSum();
        List<List<Integer>> lists = combinationSum.combinationSum(new int[]{1, 2, 3, 6, 7}, 7);
        lists.stream().forEach(System.out::println);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combination(target, candidates , 0, new ArrayList<>());
        return lists;
    }

    private void combination(int target, int[] candidates, int idx, List<Integer> combi){
        if(idx == candidates.length) return;
        if(target == 0){
            lists.add(new ArrayList<>(combi));
            return;
        }
        combination(target, candidates , idx + 1, combi);
        if(target - candidates[idx] >= 0){
            combi.add(candidates[idx]);
            combination(target - candidates[idx], candidates , idx, combi);
            combi.remove(combi.size() - 1);
        }
    }


}
